package Solutions;

import java.util.*;

/**
 * @Classname QuickSort
 * @Description TODO
 * @Date 2021/3/7 11:51
 * @Created by ASUS
 */
public class QuickSort {

    public static void sort(int[] array) {
        if (array == null || array.length < 2) return;
        helper(array, 0, array.length - 1);// 第一次遍历
    }

    private static void helper(int[] array, int start, int end) {
        if (start >= end) return;// 开始指针和终止指针一致，退出
        int target = array[end], wall = start;// target 为目标，wall为该目标值应该在的位置
        for (int i = start; i < end; i++) {// 依次遍历数组
            if (array[i] < target) {// 如果当前值比目标值小，交换，wall后移一位
                swap(array, i, wall++);
            }
        }
        swap(array, wall, end);// 交换
        helper(array, start, wall - 1);// 处理左半部分
        helper(array, wall + 1, end);// 处理右半部分
    }

    private static void swap(int[] array, int start, int end) {
        int tmp = array[start];
        array[start] = array[end];
        array[end] = tmp;
    }


    public static void main(String[] args) {
        // [2,0,2,1,1,0]
//        Map<String, String> h = new HashMap<>();
//        int[] test = new int[]{2,0,2,1,1,0};
        int[] test = new int[]{1,3,2,4,11,5,9,4,10,6};
        sort(test);
        System.out.println(Arrays.toString(test));
//        System.out.println(medianSlidingWindow(new int[]{1,2,7,7,2}, 3));
    }

    public static List<Integer> medianSlidingWindow(int[] nums, int k) {
        // write your code here
        int[] tmp = new int[k];
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - k + 1; i++) {
            for (int j = 0; j < k; j++) tmp[j] = nums[j + i];
            System.out.println(Arrays.toString(tmp));
            ans.add(getMedian(tmp));
        }
        return ans;
    }

    private static int getMedian(int[] tmp) {
        Arrays.sort(tmp);
        System.out.println("sorted:\t" + Arrays.toString(tmp));
        List<Double> doubles = new ArrayList<>();
        double[] doubles1 = doubles.stream().mapToDouble(Double::valueOf).toArray();
        if (tmp.length % 2 == 0) return tmp[tmp.length >> 1];
        else return tmp[tmp.length / 2];
    }
}
